<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Finding solutions of real constraints
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial066.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial063.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial068.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc138">9.4</A>&nbsp;&nbsp;Finding solutions of real constraints</H2>
In very simple cases, just imposing the constraints may be sufficient to
directly compute the (unique) solution. For example:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- 3 * X $= 4.
X = 1.3333333333333333__1.3333333333333335
Yes
</PRE></BLOCKQUOTE>
Other times, propagation will reduce the domains of the variables to
suitably small intervals:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- 3 * X + 2 * Y $= 4, X - 5 * Y $= 2, X $&gt;= -100.
Y = Y{-0.11764705946382902 .. -0.1176470540212896}
X = X{1.4117647026808551 .. 1.4117647063092196}
There are 2 delayed goals.
Yes
</PRE></BLOCKQUOTE>
In general though, some extra work will be needed to find the solutions of a
problem. The IC library provides two methods for assisting with this.
Which method is appropriate depends on the nature of the solutions to be
found. If it is expected that there a finite number of discrete solutions,
<A HREF="../bips/lib/ic/locate-2.html"><B>locate/2</B></A><A NAME="@default244"></A> and
<A HREF="../bips/lib/ic/locate-3.html"><B>locate/3</B></A><A NAME="@default245"></A> would be good choices. If
solutions are expected to lie in a continuous region,
<A HREF="../bips/lib/ic/squash-3.html"><B>squash/3</B></A><A NAME="@default246"></A> may be more appropriate.<BR>
<BR>
Locate works by nondeterministically splitting the domains of the variables
until they are narrower than a specified precision (in either absolute or
relative terms). Consider the problem of finding the points where two
circles intersect (see Figure&nbsp;<A HREF="#locatefig">9.4</A>). Normal propagation does not
deduce more than the obvious bounds on the variables:
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial028.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 9.4: Example of using locate/2</DIV><BR>
<BR>

<A NAME="locatefig"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- 4 $= X^2 + Y^2, 4 $= (X - 1)^2 + (Y - 1)^2.
X = X{-1.0000000000000004 .. 2.0000000000000004}
Y = Y{-1.0000000000000004 .. 2.0000000000000004}
There are 12 delayed goals.
Yes
</PRE></BLOCKQUOTE>
Calling <A HREF="../bips/lib/ic/locate-2.html"><B>locate/2</B></A><A NAME="@default247"></A> quickly determines
that there are two solutions and finds them to the desired accuracy:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- 4 $= X^2 + Y^2, 4 $= (X-1)^2 + (Y-1)^2, locate([X, Y], 1e-5).
X = X{-0.8228756603552696 .. -0.82287564484820042}
Y = Y{1.8228756448482002 .. 1.8228756603552694}
There are 12 delayed goals.
More

X = X{1.8228756448482004 .. 1.8228756603552696}
Y = Y{-0.82287566035526938 .. -0.82287564484820019}
There are 12 delayed goals.
Yes
</PRE></BLOCKQUOTE>
Squash works by deterministically cutting off parts of the domains of
variables which it determines cannot contain any solutions. In effect, it
is like a stronger version of bounds propagation. Consider the problem of
finding the intersection of two circular discs and a hyperplane (see
Figure&nbsp;<A HREF="#squashfig">9.5</A>). Again, normal propagation does not deduce more
than the obvious bounds on the variables:
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial029.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 9.5: Example of propagation using the squash algorithm</DIV><BR>
<BR>

<A NAME="squashfig"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- 4 $&gt;= X^2 + Y^2, 4 $&gt;= (X-1)^2 + (Y-1)^2, Y $&gt;= X.
Y = Y{-1.0000000000000004 .. 2.0000000000000004}
X = X{-1.0000000000000004 .. 2.0000000000000004}
There are 13 delayed goals.
Yes
</PRE></BLOCKQUOTE>
Calling <A HREF="../bips/lib/ic/squash-3.html"><B>squash/3</B></A><A NAME="@default248"></A> results in the
bounds being tightened (in this case the bounds are tight for the feasible
region, though this is not true in general):
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- 4 $&gt;= X^2 + Y^2, 4 $&gt;= (X-1)^2 + (Y-1)^2, Y $&gt;= X,
   squash([X, Y], 1e-5, lin).
X = X{-1.0000000000000004 .. 1.4142135999632601}
Y = Y{-0.41421359996326 .. 2.0000000000000004}
There are 13 delayed goals.
Yes
</PRE></BLOCKQUOTE>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">For more details, see the IC chapter of the Library Manual or the
documentation for the individual predicates.</FONT>
</DL>

<HR>
<A HREF="tutorial066.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial063.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial068.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
